home *** CD-ROM | disk | FTP | other *** search
/ OpenGL Superbible (2nd Edition) / OpenGL SuperBible e2.iso / tools / Mesa-3.0 / SRC / HASH.C < prev    next >
Encoding:
C/C++ Source or Header  |  1998-02-07  |  6.1 KB  |  297 lines
  1. /* $Id: hash.c,v 3.1 1998/02/07 14:32:57 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  3.0
  6.  * Copyright (C) 1995-1998  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: hash.c,v $
  26.  * Revision 3.1  1998/02/07 14:32:57  brianp
  27.  * fixed a small Sun compiler warning (John Stone)
  28.  *
  29.  * Revision 3.0  1998/01/31 20:53:58  brianp
  30.  * initial rev
  31.  *
  32.  */
  33.  
  34.  
  35. #ifdef PC_HEADER
  36. #include "all.h"
  37. #else
  38. #include <assert.h>
  39. #include <stdlib.h>
  40. #include <stdio.h>
  41. #include "hash.h"
  42. #endif
  43.  
  44.  
  45. /*
  46.  * Generic hash table.  Only dependency is the GLuint datatype.
  47.  *
  48.  * This is used to implement display list and texture object lookup.
  49.  * NOTE: key=0 is illegal.
  50.  */
  51.  
  52.  
  53. #define TABLE_SIZE 1001
  54.  
  55. struct HashEntry {
  56.    GLuint Key;
  57.    void *Data;
  58.    struct HashEntry *Next;
  59. };
  60.  
  61. struct HashTable {
  62.    struct HashEntry *Table[TABLE_SIZE];
  63.    GLuint MaxKey;
  64. };
  65.  
  66.  
  67.  
  68. /*
  69.  * Return pointer to a new, empty hash table.
  70.  */
  71. struct HashTable *NewHashTable(void)
  72. {
  73.    return (struct HashTable *) calloc(sizeof (struct HashTable), 1);
  74. }
  75.  
  76.  
  77.  
  78. /*
  79.  * Delete a hash table.
  80.  */
  81. void DeleteHashTable(struct HashTable *table)
  82. {
  83.    GLuint i;
  84.    assert(table);
  85.    for (i=0;i<TABLE_SIZE;i++) {
  86.       struct HashEntry *entry = table->Table[i];
  87.       while (entry) {
  88.      struct HashEntry *next = entry->Next;
  89.      free(entry);
  90.      entry = next;
  91.       }
  92.    }
  93.    free(table);
  94. }
  95.  
  96.  
  97.  
  98. /*
  99.  * Lookup an entry in the hash table.
  100.  * Input:  table - the hash table
  101.  *         key - the key
  102.  * Return:  user data pointer or NULL if key not in table
  103.  */
  104. void *HashLookup(const struct HashTable *table, GLuint key)
  105. {
  106.    GLuint pos;
  107.    struct HashEntry *entry;
  108.  
  109.    assert(table);
  110.    assert(key);
  111.  
  112.    pos = key % TABLE_SIZE;
  113.    entry = table->Table[pos];
  114.    while (entry) {
  115.       if (entry->Key == key) {
  116.      return entry->Data;
  117.       }
  118.       entry = entry->Next;
  119.    }
  120.    return NULL;
  121. }
  122.  
  123.  
  124.  
  125. /*
  126.  * Insert into the hash table.  If an entry with this key already exists
  127.  * we'll replace the existing entry.
  128.  * Input:  table - the hash table
  129.  *         key - the key (not zero)
  130.  *         data - pointer to user data
  131.  */
  132. void HashInsert(struct HashTable *table, GLuint key, void *data)
  133. {
  134.    /* search for existing entry with this key */
  135.    GLuint pos;
  136.    struct HashEntry *entry;
  137.  
  138.    assert(table);
  139.    assert(key);
  140.  
  141.    if (key > table->MaxKey)
  142.       table->MaxKey = key;
  143.  
  144.    pos = key % TABLE_SIZE;
  145.    entry = table->Table[pos];
  146.    while (entry) {
  147.       if (entry->Key == key) {
  148.          /* replace entry's data */
  149.      entry->Data = data;
  150.      return;
  151.       }
  152.       entry = entry->Next;
  153.    }
  154.  
  155.    /* alloc and insert new table entry */
  156.    entry = (struct HashEntry *) calloc(sizeof(struct HashEntry), 1);
  157.    entry->Key = key;
  158.    entry->Data = data;
  159.    entry->Next = table->Table[pos];
  160.    table->Table[pos] = entry;
  161. }
  162.  
  163.  
  164.  
  165. /*
  166.  * Remove an entry from the hash table.
  167.  * Input:  table - the hash table
  168.  *         key - key of entry to remove
  169.  */
  170. void HashRemove(struct HashTable *table, GLuint key)
  171. {
  172.    GLuint pos;
  173.    struct HashEntry *entry, *prev;
  174.  
  175.    assert(table);
  176.    assert(key);
  177.  
  178.    pos = key % TABLE_SIZE;
  179.    prev = NULL;
  180.    entry = table->Table[pos];
  181.    while (entry) {
  182.       if (entry->Key == key) {
  183.          /* found it! */
  184.          if (prev) {
  185.             prev->Next = entry->Next;
  186.          }
  187.          else {
  188.             table->Table[pos] = entry->Next;
  189.          }
  190.          free(entry);
  191.      return;
  192.       }
  193.       prev = entry;
  194.       entry = entry->Next;
  195.    }
  196. }
  197.  
  198.  
  199.  
  200. /*
  201.  * Return the key of the "first" entry in the hash table.
  202.  * By calling this function until zero is returned we can get
  203.  * the keys of all entries in the table.
  204.  */
  205. GLuint HashFirstEntry(const struct HashTable *table)
  206. {
  207.    GLuint pos;
  208.    assert(table);
  209.    for (pos=0; pos < TABLE_SIZE; pos++) {
  210.       if (table->Table[pos])
  211.          return table->Table[pos]->Key;
  212.    }
  213.    return 0;
  214. }
  215.  
  216.  
  217.  
  218. /*
  219.  * Dump contents of hash table for debugging.
  220.  */
  221. void HashPrint(const struct HashTable *table)
  222. {
  223.    GLuint i;
  224.    assert(table);
  225.    for (i=0;i<TABLE_SIZE;i++) {
  226.       struct HashEntry *entry = table->Table[i];
  227.       while (entry) {
  228.      printf("%u %p\n", entry->Key, entry->Data);
  229.      entry = entry->Next;
  230.       }
  231.    }
  232. }
  233.  
  234.  
  235.  
  236. /*
  237.  * Find a block of 'numKeys' adjacent unused hash keys.
  238.  * Input:  table - the hash table
  239.  *         numKeys - number of keys needed
  240.  * Return:  startint key of free block or 0 if failure
  241.  */
  242. GLuint HashFindFreeKeyBlock(const struct HashTable *table, GLuint numKeys)
  243. {
  244.    GLuint maxKey = ~((GLuint) 0);
  245.    if (maxKey - numKeys > table->MaxKey) {
  246.       /* the quick solution */
  247.       return table->MaxKey + 1;
  248.    }
  249.    else {
  250.       /* the slow solution */
  251.       GLuint freeCount = 0;
  252.       GLuint freeStart = 0;
  253.       GLuint key;
  254.       for (key=0; key!=maxKey; key++) {
  255.      if (HashLookup(table, key)) {
  256.         /* darn, this key is already in use */
  257.         freeCount = 0;
  258.         freeStart = key+1;
  259.      }
  260.      else {
  261.         /* this key not in use, check if we've found enough */
  262.         freeCount++;
  263.         if (freeCount == numKeys) {
  264.            return freeStart;
  265.         }
  266.      }
  267.       }
  268.       /* cannot allocate a block of numKeys consecutive keys */
  269.       return 0;
  270.    }
  271. }
  272.  
  273.  
  274.  
  275. #ifdef HASH_TEST_HARNESS
  276. int main(int argc, char *argv[])
  277. {
  278.    int a, b, c;
  279.    struct HashTable *t;
  280.  
  281.    printf("&a = %p\n", &a);
  282.    printf("&b = %p\n", &b);
  283.  
  284.    t = NewHashTable();
  285.    HashInsert(t, 501, &a);
  286.    HashInsert(t, 10, &c);
  287.    HashInsert(t, 0xfffffff8, &b);
  288.    HashPrint(t);
  289.    printf("Find 501: %p\n", HashLookup(t,501));
  290.    printf("Find 1313: %p\n", HashLookup(t,1313));
  291.    printf("Find block of 100: %d\n", HashFindFreeKeyBlock(t, 100));
  292.    DeleteHashTable(t);
  293.  
  294.    return 0;
  295. }
  296. #endif
  297.